山峰和山谷
题目 山峰和山谷
FGD小朋友特别喜欢爬山，在爬山的时候他就在研究山峰和山谷。
为了能够对旅程有一个安排，他想知道山峰和山谷的数量。
给定一个地图，为FGD想要旅行的区域，地图被分为 n * n 的网格，每个格子 (i,j)的高度 w(i,j)是给定的。
若两个格子有公共顶点，那么它们就是相邻的格子，如与 (i,j)(i,j)(i,j) 相邻的格子有(i−1,j−1),(i−1,j),(i−1,j+1),(i,j−1),(i,j+1),(i+1,j−1),(i+1,j),(i+1,j+1)
我们定义一个格子的集合 S 为山峰（山谷）当且仅当：
- S 的所有格子都有相同的高度。
- S 的所有格子都连通。
- 对于 s 属于 S，与 s 相邻的 s’不属于 S，都有 ws>ws′（山峰），或者 ws<ws′（山谷）。
- 如果周围不存在相邻区域，则同时将其视为山峰和山谷。
你的任务是，对于给定的地图，求出山峰和山谷的数量，如果所有格子都有相同的高度，那么整个地图即是山峰，又是山谷。
输入格式
第一行包含一个正整数 nnn，表示地图的大小。
接下来一个 n * n 的矩阵，表示地图上每个格子的高度 w。
输出格式
共一行，包含两个整数，表示山峰和山谷的数量。
数据范围
输入样例1：
5
8 8 8 7 7
7 7 8 8 7
7 7 7 7 7
7 8 8 7 8
7 8 8 8 8
输出样例1：
2 1
输入样例2：
5
5 7 8 3 1
5 5 7 6 6
6 6 6 2 8
5 7 2 5 8
7 1 0 1 7
输出样例2：
3 3
样例解释
样例1：
样例2：
思路分析
暴搜所有一个点之间所有高度相等的点，如果周围的点都高于或低于当前点，那么这个就是一个山谷或山峰
代码实现
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
const int N=1010;
int h[N][N];
bool st[N][N];
int n;
int dx[8]={-1,-1,0,1,1,1,0,-1};
int dy[8]={0,1,1,1,0,-1,-1,-1};
bool isVaild(int x,int y){
return x>=0 && x<=n-1 && y>=0 && y<=n-1;
}
void dfs(int x,int y,bool &havehigher,bool &havelower){
for(int i=0;i<8;i++){
int nx=x+dx[i],ny=y+dy[i];
if(isVaild(nx,ny)){
if(h[nx][ny]>h[x][y])
havehigher=true;
if(h[nx][ny]<h[x][y])
havelower=true;
if(h[nx][ny]==h[x][y] && !st[nx][ny]){
st[nx][ny]=true;
dfs(nx,ny,havehigher,havelower);
}
}
}
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>h[i][j];
}
}
int peak=0,valley=0;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(!st[i][j]){
bool havehigher=false,havelower=false;
st[i][j]=true;
dfs(i,j,havehigher,havelower);
if(!havehigher)//如果旁边没有更高的 它就是峰地
peak++;
if(!havelower)//如果旁边没有更矮的 它就是谷底
valley++;
}
}
}
cout<<peak<<" "<<valley<<endl;
return 0;
}
八方向还可以这样写
#include <iostream>
using namespace std;
const int N = 1010;
int n;
int h[N][N];
bool st[N][N];
void dfs(int x, int y, bool& has_higher, bool& has_lower) {
st[x][y] = true; // 标记当前点已访问
for (int i = x - 1; i <= x + 1; i++) {
for (int j = y - 1; j <= y + 1; j++) {
if (i < 1 || i > n || j < 1 || j > n) continue;
if (h[i][j] > h[x][y]) has_higher = true;
else if (h[i][j] < h[x][y]) has_lower = true;
else if (!st[i][j]) dfs(i, j, has_higher, has_lower);
}
}
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
cin >> h[i][j];
int peak = 0, valley = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (!st[i][j]) {
bool has_higher = false, has_lower = false;
dfs(i, j, has_higher, has_lower);
if (!has_higher) peak++;
if (!has_lower) valley++;
}
}
}
cout << peak << ' ' << valley << endl;
return 0;
}
💬 评论